DESCRIPTION

Merge Sort is a sorting algorithm based on the Divide et Impera technique, like Quick Sort. It can be implemented iteratively or recursively, using the Top-Down and Bottom-Up algorithms respectively.

Merge sort works by dividing an array into smaller subarrays, sorting each subarray, and then merging the sorted subarrays back together to form the final sorted array.

COMPLEXITY

IMPLEMENTATIONS

void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0;
    j = 0;
    k = l;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r)
{
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}
              

function mergeSort(array) 
{
    const half = array.length / 2
    if (array.length < 2)
    {
      return array
    }
  
    const left = array.splice(0, half)
    return merge(mergeSort(left),mergeSort(array))
  }
  
  function merge(left, right) 
{
      let arr = []

      while (left.length && right.length) 
      {
          if (left[0] < right[0]) 
          {
              arr.push(left.shift())
          } 
          else 
          {
              arr.push(right.shift())
          }
      }
  
      return [ ...arr, ...left, ...right ]
  }